package Greed;

//单调递增的数字
public class MonotoneIncreasingDigits {
    //1.从前往后，找到第一个递减的位置
    //从这个位置向前推，后面的数都修改成9
    public int monotoneIncreasingDigits(int n) {
        String s=Integer.toString(n);
        char[] c=s.toCharArray();
        int i=0,m=c.length;
        //递增
        while(i+1<m && c[i]<=c[i+1]){
            i++;
        }
        if(i==m-1) return n;
        //回退
        while(i-1>=0 && c[i-1]==c[i]){
            i--;
        }
        c[i]--;
        for (int j = i+1; j < m; j++) {
            c[j]='9';
        }
        return Integer.parseInt(new String(c));
    }
}
